package leetcode

import (
	"math"
)

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func minDepth1(root *TreeNode) int {
	return min(root, true)
}

func min(root *TreeNode, empty bool) int {
	if root == nil {
		if empty {
			return 0
		}
		return math.MaxInt64
	}

	l := min(root.Left, root.Right == nil)
	r := min(root.Right, root.Left == nil)
	if l > r {
		return r + 1
	}
	return l + 1
}

func minDepth(root *TreeNode) int {
	if root == nil {
		return 0
	}

	q, next, n, depth, i := []*TreeNode{root}, make([]*TreeNode, 0, 2), new(TreeNode), 1, 0
	for {
		n, i = q[i], i+1

		if n.Left != nil {
			if n.Left.Left == nil && n.Left.Right == nil {
				return depth + 1
			}
			next = append(next, n.Left)
		}
		if n.Right != nil {
			if n.Right.Left == nil && n.Right.Right == nil {
				return depth + 1
			}
			next = append(next, n.Right)
		}

		if i < len(q) {
			continue
		}

		if len(next) == 0 {
			break
		}

		q, next, depth, i = next, q[:0], depth+1, 0
	}

	return depth
}
